public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length <= 0) {
            return "";
        }

        String first = strs[0];
        List<String> preList = new ArrayList<>(first.length());
        for (int i = 0; i < first.length(); i++) {
            preList.add(first.substring(0, i + 1));
        }

        int max = -1;
        for (int i = 1; i < strs.length; i++) {
            int tmpMax = -1;
            String str = strs[i];
            for (int j = 0; j < preList.size(); j++) {
                if (str.startsWith(preList.get(j))) {
                    tmpMax = i;
                } else {
                    break;
                }
            }

            if (tmpMax == -1) {//没有匹配成功的前缀，直接结束
                max = -1;
                break;
            }

            if (max == -1) {
                max = tmpMax;
            } else {
                max = Math.min(max, tmpMax);
            }
        }

        return max == -1 ? "" : preList.get(max);
    }
}